package com.mlh.binarytree;

/**
 * @author 缪林辉
 * @date 2024/3/28 10:21
 * @DESCRIPTION
 */

// 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。
// 判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
// 如果存在，返回 true ；否则，返回 false 。
public class 路径总和 {
    //DFS 遇到叶子节点 就对比一下加起来的总和，总和和目标总一样就返回true
    public boolean method1(TreeNode root, int targetSum) {
        return recursion(root,0,targetSum);
    }

    public boolean recursion(TreeNode node,int curSum,int targetSum){
        if(node==null){
            return false;
        }
        if(node.right==null&&node.left==null&&curSum+node.val==targetSum){
            return true;
        }
        curSum=curSum+node.val;
        boolean res1= recursion(node.left,curSum,targetSum);
        boolean res2= recursion(node.right,curSum,targetSum);
        return res1||res2;//只要有一个true 最终答案就是true
    }

    //利用先序遍历来访问一条根节点到叶子节点的路径
    public boolean practice(TreeNode root, int targetSum) {
        if(root==null){
            return false;
        }
        return recursionPractice(root,0,targetSum);
    }

    private boolean recursionPractice(TreeNode root, int pathSum, int targetSum) {
        if(root==null){
            return false;
        }
        pathSum+=root.val;
        if(pathSum==targetSum&&root.left==null&& root.right==null){
            return true;
        }
        return recursionPractice(root.left,pathSum,targetSum)||recursionPractice(root.right,pathSum,targetSum);
    }
}
